package it.uniroma2.util.vector;


import it.uniroma2.util.math.ArrayMath;
import it.uniroma2.util.math.Complex;
import it.uniroma2.util.math.FFT;

import java.util.Arrays;
import java.util.Random;

/**
 * @author lorenzo
 * This class provides several vector composition operations.
 * Among them are the shuffled circular convolution and shuffled gamma-product described in the paper.
 * Their parameters are generated just once at initialization.
 */
public class VectorComposer {
	
	public double gamma = 0;	// Gamma parameter for the shuffled gamma-product
	public int[] permutation1;	// Permutation p_1 of shuffled gamma-product and shuffled circular convolution
	public int[] permutation2;	// Permutation p_2 of shuffled gamma-product and shuffled circular convolution
	public FFT fft = null;		// Object used to optionally compute the Fast Fourier Transform for the circular convolutions
	public int spaceGrade = 0;	// log_2 of the vector dimension, where an integer, for using the FFT
	
	public VectorComposer() {}
	
	public VectorComposer(VectorProvider vp) throws Exception {
		initialize(vp);
	}
	
	public void initializeFFT(int vectorSize) {
		int exp = log2(vectorSize);
		if (exp < 0)
			return;
		else {
			fft = new FFT();
			fft.initialize(exp);
			spaceGrade = exp;
		}
	}
	
	public void initializeGamma(VectorProvider vp) throws Exception {
		for (int i=0;i<1000;i++) {
			gamma += ArrayMath.norm(product(vp.generateRandomVector(), vp.generateRandomVector()));
		}
		gamma = gamma/1000;
	}
	
	/**
	 * Initialization of the parameters gamma, p_1, p_2 and, possibly, the FFT environment.
	 * The initialization depends on the vectors size.
	 * @param vp - the VectorProvider that will be used for getting the vectors to be composed
	 * @throws Exception
	 */
	public void initialize(VectorProvider vp) throws Exception {
		int size = vp.generateRandomVector().length;
		permutation1 = generatePermutation(size, 0, null);
		permutation2 = generatePermutation(size, 1, permutation1);
		initializeGamma(vp);
		initializeFFT(size);
	}
	
	public double[] sum(double[] firstVector, double[] secondVector)
	{
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		for (int i=0; i<size; i++)
			result[i] = firstVector[i] + secondVector[i];
		return result;
	}
	
	public double[] product(double[] firstVector, double[] secondVector)
	{
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		for (int i=0; i<size; i++)
			result[i] = firstVector[i] * secondVector[i];
		return result;
	}
	
	public double[] circularConvolution(double[] firstVector, double[] secondVector)
	{
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		Arrays.fill(result, 0);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++)
				result[i] += firstVector[j] * secondVector[(i-j)<0 ? (i-j+size) : i-j];
		return result;
	}
	
	public double[] reverseProduct(double[] firstVector, double[] secondVector)
	{
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		for (int i=0; i<size; i++)
			result[i] = firstVector[i] * secondVector[size - 1 - i];
		return result;
	}
	
	public double[] reverseGammaProduct(double[] firstVector, double[] secondVector) throws Exception
	{
		return ArrayMath.scalardot(1/gamma, reverseProduct(firstVector, secondVector));
	}
	
	public double[] reverseConvolution(double[] firstVector, double[] secondVector)
	{
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		Arrays.fill(result, 0);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++)
				result[i] += firstVector[j] * secondVector[(i-j)<0 ? size-1-(i-j+size) : size-1-(i-j)];
		return result;
	}
	
	public double[] shiftedProduct(double[] firstVector, double[] secondVector)
	{
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		result[0] = firstVector[0] * secondVector[size-1];
		for (int i=1; i<size; i++)
			result[i] = firstVector[i] * secondVector[i-1];
		return result;
	}
	
	public double[] shiftedGammaProduct(double[] firstVector, double[] secondVector) throws Exception
	{
		return ArrayMath.scalardot(1/gamma, shiftedProduct(firstVector, secondVector));
	}
	
	public double[] shiftedConvolution(double[] firstVector, double[] secondVector) {
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		Arrays.fill(result, 0);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++) {
				int k = (i-j) < 0 ? (i-j+size) : i-j;
				result[i] += firstVector[j] * secondVector[(k>0) ? k-1 : size-1];
			}
		return result;
	}
	
	public double[] shift(double[] vector)
	{
		if (vector == null)
			return null;
		int size = vector.length;
		double[] result = new double[size];
		result[0] = vector[size-1];
		for (int i=1; i<size; i++)
			result[i] = vector[i-1];
		return result;
	}
	
	public double[] shuffledProduct(double[] firstVector, double[] secondVector) {
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		for (int i=0; i<size; i++)
			if (permutation1[i] >= 0) {
				if (permutation2[i] >= 0)
					result[i] = firstVector[permutation1[i]] * secondVector[permutation2[i]];
				else
					result[i] = firstVector[permutation1[i]] * -secondVector[-permutation2[i]];
			}
			else {
				if (permutation2[i] >= 0)
					result[i] = -firstVector[-permutation1[i]] * secondVector[permutation2[i]];
				else
					result[i] = -firstVector[-permutation1[i]] * -secondVector[-permutation2[i]];
			}
		return result;
	}
	
	public double[] shuffledGammaProduct(double[] firstVector, double[] secondVector) throws Exception
	{
		return ArrayMath.scalardot(1/gamma, shuffledProduct(firstVector, secondVector));
	}

	
	public double [] shuffledConvolutionFFT(double[] firstVector, double[] secondVector) {
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		if (fft == null)
			throw new RuntimeException("FFT not initialized - is dimension power of 2?");
		return Complex.extract(fft.real_cconvolve(
						Complex.generate(shuffle(firstVector, permutation1)),
						Complex.generate(shuffle(secondVector, permutation2)),
						spaceGrade));
	}
	
	public double[] shuffledConvolution(double[] firstVector, double[] secondVector) {
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] result = new double[size];
		Arrays.fill(result, 0);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++) {
				int k = (i-j) < 0 ? (i-j+size) : i-j;
				if (permutation1[j] >= 0) {
					if (permutation2[k] >= 0)
						result[i] += firstVector[permutation1[j]] * secondVector[permutation2[k]];
					else
						result[i] += firstVector[permutation1[j]] * -secondVector[-permutation2[k]];
				}
				else {
					if (permutation2[k] >= 0)
						result[i] += -firstVector[-permutation1[j]] * secondVector[permutation2[k]];
					else
						result[i] += -firstVector[-permutation1[j]] * -secondVector[-permutation2[k]];
				}
			}
		return result;
	}
	
	public double[] shuffle(double[] vector, int[] permutation) {
		if (vector.length != permutation.length)
			return null;
		double[] shuffled = new double[vector.length];
		for (int i=0; i<vector.length; i++)
			if (permutation[i] >= 0)
				shuffled[i] = vector[permutation[i]];
			else
				shuffled[i] = -vector[-permutation[i]];
		return shuffled;
	}
	
	public double[] matrixProduct(double[] firstVector, double[] secondVector, 
			double[][] firstMatrix, double[][] secondMatrix) {
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] firstTranslated = new double[size];
		Arrays.fill(firstTranslated, 0);
		double[] secondTranslated = new double[size];
		Arrays.fill(secondTranslated, 0);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++) {
				firstTranslated[i] += firstVector[j] * firstMatrix[i][j];
				secondTranslated[i] += secondVector[j] * secondMatrix[i][j];
			}
		return product(firstTranslated, secondTranslated);
	}
	
	public double[] matrixConvolution(double[] firstVector, double[] secondVector, 
			double[][] firstMatrix, double[][] secondMatrix) {
		if (firstVector == null)
			return secondVector;
		else if (secondVector == null)
			return firstVector;
		int size = firstVector.length;
		double[] firstTranslated = new double[size];
		Arrays.fill(firstTranslated, 0);
		double[] secondTranslated = new double[size];
		Arrays.fill(secondTranslated, 0);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++) {
				firstTranslated[i] += firstVector[j] * firstMatrix[i][j];
				secondTranslated[i] += secondVector[j] * secondMatrix[i][j];
			}
		return circularConvolution(firstTranslated, secondTranslated);
	}
	
	public int[] generatePermutation(int size, int seed, int[] anotherPermutation) {
		Random rand = new Random(seed);
		int[] permutation = generateRandomPermutation(size, rand);
		while (!testPermutation(permutation, anotherPermutation)) {
			System.out.println("Discarding permutation!");
			permutation = generateRandomPermutation(size, rand);
		}
		return permutation;
	}
	
	public int[] generateRandomPermutation(int size, Random rand) {
		int[] permutation = new int[size];
		double[] toOrder = new double[size];;
		for (int i=0; i<size; i++)
			toOrder[i] = rand.nextGaussian();
		double[] ordered = Arrays.copyOf(toOrder, size);
		Arrays.sort(ordered);
		for (int i=0; i<size; i++)
			for (int j=0; j<size; j++)
				if (toOrder[i] == ordered[j]) {
					permutation[i] = toOrder[i]<0 ? -j : j;
					break;
				}
		return permutation;
	}
	
	/**
	 * The permutation is valid if its cycle is long enough, 
	 * and, optionally, if it is not equal or the inverse of another given permutation
	 */
	private boolean testPermutation(int[] permutation, int[] anotherPermutation) {
		double[] basic = new double[permutation.length];
		for (int i=0; i<basic.length; i++)
			basic[i] = i;
		double[] shuffled = Arrays.copyOf(basic, basic.length);
		for (int i=0; i<basic.length; i++) {
			shuffled = shuffle(shuffled, permutation);
			if (Arrays.equals(shuffled, basic))
				return false; 
			if (anotherPermutation != null) {
				if (Arrays.equals(shuffled, shuffle(basic, anotherPermutation)))
					return false;
				if (Arrays.equals(basic, shuffle(shuffled, anotherPermutation)))
					return false;
			}
		}
		return true;
	}
	
	public double[] shuffledProduct(double[] x, double[] y,
			int[] permutation_x, int[] permutation_y) {
		double [] out = new double[x.length];
		
		for (int i = 0; i < x.length;i++) 
			out[i] = x[permutation_x[i]] * y[permutation_y[i]];
		
		return out;
	}
	
	private int log2(int arg) {
		int exp = 0;
		while(true) {
			double pow = Math.pow(2, exp); 
			if (pow == arg)
				return exp;
			else if (pow > arg)
				return -1;
			exp++;
		}
	}
}
